As known in the art, the fast Fourier transform (FFT) has application in many technologies for performing signal analysis such as power spectrum analysis and filter simulation by means of digital computers. For example, FFT processors are commonly used in radar systems for pulse compression and Doppler processing. The Fourier relation is said to map a signal from the time domain into the frequency domain. Conversely, the inverse Fourier relation is said to map from the frequency domain to the time domain. Specifically, in a radar system, the video output of the radar receiver is typically time sampled, each sample being converted into a digital word. It is common for a radar receiver to have two video outputs that are 90.degree. out of phase and called "inphase" and "quadrature" in which case both are simultaneously sampled and digitized. Digital words which may comprise a real part corresponding to the "inphase" channel and an imaginary part corresponding to the "quadrature" channel are processed in parallel form through an FFT processor to produce another set of digital words which correspond to discrete frequency components of the frequency spectrum of the received radar signal.
The FFT is a method for efficiently computing the discrete Fourier transform (DFT) of a series of data samples referred to as a time series. The discrete Fourier transform is defined as ##EQU1## where F.sub.(k) is the kth component of the DFT, s(n) denotes the nth sample of the time series consisting of N complex samples; n=0,1, 2, . . . , N-1, and j=-1. Briefly, an FFT is an algorithm which provides a relatively fast means of computing a DFT by reducing the number of operations from approximately N.sup.2 to 2Nlog.sub.2 N as compared to a DFT; this is generally accomplished by reducing the redundant operations and of course also provides a corresponding descrease in computation processing time.
Referring to FIG. 1, a signal flow graph is shown that illustrates the computation of a FFT. The inputs, s(0) through s(7) and generally s(n), are a time series of discrete samples. As is well known, such a time series completely represents the continuous waveform provided the waveform is frequency band limited and the samples are taken at a rate that is least twice the highest frequency present in the waveform. It is common to call the samples Nyquist if they are equally spaced and twice the highest frequency. It is noted that the time series is not incrementally ordered from top to bottom; this is referred to as bit reversal, the function of which is to provide "in place" calculations as described by William T. Cochran et al, Proceedings of the IEEE, volume 55, No. 10, October 1967 at page 1670. It is also noted that in radar system applications, the inputs are frequently complex numbers or vector quantities with the real part corresponding to the inphase channel of the receiver and the imaginary part corresponding to the quadrature channel. The number of bits in the digital words of the inputs determines the dynamic range of the system.
The basic building block of an FFT as shown in FIG. 1 is a vector rotation by a complex weighting coefficient, W.sub.n, and a sum and difference of the result with another vector. If the unrotated vector is A=R.sub.1 +jI.sub.1, the rotated vector is B=R.sub.2 +jI.sub.2, and W.sub.n =e.sup.-j.theta., the output of the basic building block is given by the following equations. EQU A'=R.sub.1 +(R.sub.2 cos .theta.+I.sub.2 sin .theta.)+j[I.sub.1 +(I.sub.2 cos .theta.-R.sub.2 sin .theta.)] EQU B'=R.sub.1 -(R.sub.2 cos .theta.+I.sub.2 sin .theta.)+j[I.sub.1 -(I.sub.2 cos .theta.-R.sub.2 sin .theta.)]
As can be seen from the equation above, A' and B' can be calculated in a digital computer by a combination of four multiplies and six adds in addition to looking up the trigonometric values in a table. This conventional method of calculation, however, is not fast enough to permit a FFT throughput rate as required by some applications. For example, in radar FFT processing with a waveform of increased time-bandwidth product, an FFT with an increased number of points may be required thus reducing the time allocated for the calculation of each of the basic building blocks.
Recently, the coordinate rotation digital computer (CORDIC) technique was introduced as a method of calculating a vector rotated through a given angle. This technique has also been applied to FFT's. However, there is still a need for a CORDIC unit and a digital processor in general wherein increased throughputs can be realized.
Furthermore, some applications require that an FFT processor with a high throughput rate also have the capability to be programmable such that FFT's of different numbers of points can be performed.